Prof. Domenico Luminati
Anno Accademico 2001/2002
- 1. Insiemi e cardinalità
- Insiemi, unione, intersezione, prodotto cartesiano, relazioni, funzioni parziali e totali
- L'insieme potenza e il teorema di Cantor
- Confronto tra cardinalità: il teorema di Cantor-Bernstein
- Assiomi di Peano dei numeri naturali. Principio di induzione
- Teorema di ricorsione, definizione delle operazioni e dell'ordinamento dei naturali
- Il lemma dei cassetti e la definizione di cardinalità degli insiemi finiti
- L'assioma di scelta
- Insiemi numerabili
- Operazioni tra cardinalità e calcolo della cardinalità di alcuni insiemi finiti (prodotto cartesiano, applicazioni, parti, combinazioni, disposizioni, permutazioni)
- 2. Aritmetica
- Divisione euclidea ed espressione in base arbitraria degli interi
- DIvisibilità, MCD e MCM, numeri primi e teorema di fattorizzazione unica
- Congruenze, classi di resto, e operazioni tra classi di congruenza.
- Il teorema cinese dei resti
- Elementi invertibili modulo n, piccolo teorema di Fermat, cenno alla crittografia RSA
- 3. Grafi
- Grafi, sottografi, isomorfismo di grafi
- Passeggiate, cammini, cicli
- Connessione, componenti connesse di un grafo
- Grafi euleriani e loro caratterizzazione
- Cenni sui grafi hamiltoniani
- 2-connessione, e teoremi di caratterizzazione della 2-connessione
- alberi, teorema di caratterizzazione degli alberi
- alberi di copertura, teorema di esistenza degli alberi di copertura
- Alberi radicati, ordinamento degli alberi radicati, induzione sugli alberi radicati
- Il lemma di Koenig
- Testi consigliati
- N. L. Biggs, Discrete Mathematics, Oxfors Science Publications,1998
- J. Matousek, J. Nesetril, Invitation to Discrete Mathematics, Oxford University Press, 1998
- P. J. Cameron, Combinatorics: Topics, tecniques, algorithms, Cambridge University Press
- A. Facchini, Algebra